#include <dbg.h>

#include <cassert>
using namespace std;

class Solution {
public:
    int maxTotalFruits(vector<vector<int>>& fruits, int startPos, int k) {
        int res = 0;
        int sum = 0;
        int n = fruits.size();
        auto cmp = [](const vector<int>& a, int b) { return a[0] < b; };
        int left =
            lower_bound(fruits.begin(), fruits.end(), startPos - k, cmp) -
            fruits.begin();  // 找到第一个不小于 startPos - k 的位置
        for (int right = left; right < n && fruits[right][0] <= startPos + k;
             ++right) {
            sum += fruits[right][1];  // 累加水果数量
            dbg(sum, left, right);
            while (fruits[right][0] * 2 - fruits[left][0] - startPos > k &&
                   fruits[right][0] - fruits[left][0] * 2 + startPos >
                       k) {              // 检查窗口是否满足步数限制
                sum -= fruits[left][1];  // 移动左边界
                ++left;
                dbg(sum, left, right);
            }
            res = max(res, sum);  // 更新最大值
        }
        return res;
    }
};

int main() {
    Solution s;

    vector<vector<int>> fruits1 = {{2, 8}, {6, 3}, {8, 6}};
    vector<vector<int>> fruits2 = {
        {0, 9}, {4, 1}, {5, 7}, {6, 2}, {7, 4}, {10, 9}};
    vector<vector<int>> fruits3 = {{0, 3}, {6, 4}, {8, 5}};

    int startPos1 = 5;
    int startPos2 = 5;
    int startPos3 = 3;

    int k1 = 4;
    int k2 = 4;
    int k3 = 2;

    assert(s.maxTotalFruits(fruits1, startPos1, k1) == 9);
    assert(s.maxTotalFruits(fruits2, startPos2, k2) == 14);
    assert(s.maxTotalFruits(fruits3, startPos3, k3) == 0);

    return 0;
}